You have a queue of integers, you need to retrieve the first unique integer in the queue.
Implement the FirstUnique class:
FirstUnique(int[] nums)Initializes the object with the numbers in the queue.int showFirstUnique()returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.void add(int value)insert value to the queue.
Example 1:
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2); // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3); // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1
Example 2:
Input: ["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"] [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]] Output: [null,-1,null,null,null,null,null,17] Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17); // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17
Example 3:
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]] Output: [null,809,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^81 <= value <= 10^8- At most
50000calls will be made toshowFirstUniqueandadd.
Average Rating: 4.62 (21 votes)
Solution
Approach 1: Brute Force
Intuition
The simplest solution for this problem is to create a queue as normal, and then search through it to find the first unique number.
We do this by looping through the items in the queue (starting from the oldest). For each item, we loop through the queue again, counting how many times it appears. If it only appears once, we stop and return it. If there are no items that appear only once, then we return -1.
Algorithm
We don't need to implement counting ourselves; we can use Collections.frequency(...) in Java, and .count(...) in Python.
Complexity Analysis
Let K be the length of the initial array passed into the constructor. Let N be the total number of items added onto the queue so far (including those from the constructor).
-
Time complexity :
-
constructor: O(K).
We create a new copy of the passed in numbers; this has a cost of O(K) time to create.
-
add(): O(1).
We perform a single append to a queue; this has a cost of O(1).
-
showFirstUnique(): O(N2).
Counting how many times a given item appears in the queue has a cost of O(N). This is true even for the library functions we're using.
In the worst case, we search through the entire queue without finding a unique number. At a cost of O(N) each time, this gives us a cost of O(N2).
-
-
Space complexity : O(N).
The memory used is simply the total number of items currently in the queue.
Approach 2: Queue and HashMap of Unique-Status
Intuition
When given a data-structure-design question like this one, a good strategy is to start simple and identify where the inefficiencies are.
In Approach 1, we performed numerous count operations; each call to showFirstUnique() performed, in the worst case, N count operations. At a cost of O(N) per count, this was expensive! These count-ups are also repetitive, and so should be our focus for optimization.
When deciding whether or not to return a particular number, all we need to know is whether or not that number is unique. In other words, we only want to know whether it has occurred "once", or "more than once". Seeing as numbers cannot be removed from the FirstUnique data structure, we know that once a particular number is added for the second time, that number will never again be unique.
So, instead of counting how many times a number occurred in the queue, we could instead keep a HashMap of numbers to booleans, where for each number that has been added, we're storing the answer to the question is this number unique?. We'll call it isUnique. Then, when FirstUnique.add(number) is called, one of three cases will apply:
-
This particular number has never been seen before now. Add it to
isUniquewith a value oftrue. Also, add it to the queue. -
This particular number has already been seen by
isUnique, with a value oftrue. This means that the number was previously unique (and is currently in the queue), but with this new addition, it no longer is. Update its value tofalse. Do not add it to the queue. -
This particular number has already been seen by
isUnique, with a value offalse. This means that it has already been seen twice before. We don't need to do anything, and shouldn't add it to the queue.
Then, instead of needing to perform "count" operations, the showFirstUnique() can simply look in isUnique for the information it needs.
Here is an animation showing how this works so far.
This is a good start. However, you might have noticed another inefficiency while watching the animation: the 7 at the front needs to be stepped passed on every call to showFirstUnique(). As soon as the second 7 was added, though, this 7 was no longer unique, and so would never be the answer to a call to showFirstUnique() again (remember, this queue has no deletion operation). Therefore, there is no reason to leave it in the queue—we should remove it so that we don't keep looking at it.
But, where should we actually do these removals from the queue? In showFirstUnique(), or in add()?
-
If we do a removal in the
add()method, we'll need to do an O(N) search of the queue to find the number, and then potentially another to remove it from the queue, (if you're chosen programming language even supports deletions from the middle of a queue!). -
If we do the removal in the
showFirstUnique()method, we might sometimes need to do lots of removals before we find a unique number to return. However, it will be faster across all calls to the data structure, because we didn't need to do a search to find the non-unique number like we would have withadd(). We'll talk more about this in the time complexity section.
So, our best option is to do the removals in the showFirstUnique() method.
We should leave the number's value as false in isUnique, though. Like we said above, a number can never "become" unique again.
Here is an animation showing the full algorithm.
Algorithm
Complexity Analysis
Let K be the length of the initial array passed into the constructor.
Let N be the total number of items added onto the queue so far (including those from the constructor).
-
Time complexity :
-
constructor: O(K).
For each of the K numbers passed into the constructor, we're making a call to
add(). As we will determine below, each call toadd()has a cost of O(1). Therefore, for the K numbers added in the constructor, we get a total cost of K⋅O(1)=O(K). -
add(): O(1).
We check the status of the number in a
HashMap, which is an O(1) operation. We also optionally modify its status in theHashMap, which, again, is an O(1) operation.Depending on the status of the number, we add it to the queue, which is again, an O(1) operation.
Therefore, we get an O(1) time complexity for the
add()method. -
showFirstUnique(): O(1) (amortized).
For this implementation, the
showFirstUnique()method needs to iterate down the queue until it finds a unique number. For each unique number it encounters along the way, it removes it. Removing an item from a queue has a cost of O(1). The total number of these removals we need to carry out is proportional to the number of calls toadd(), because eachadd()corresponds to at most one removal that will ultimately have to happen. Then when we find a unique number, it is an O(1) operation to return it.Because the number of O(1) removals is proportional to the number of calls to
add(), we say that the time complexity amortizes across all calls toadd()andshowFirstUnique(), giving an overall time complexity of O(1) (amortized).If you're not familiar with amortized time complexity, check out the Wikipedia page.
-
-
Space complexity : O(N).
Each number is stored up to once in the queue, and up to once in the HashMap. Therefore, we get an overall space complexity of O(N).
Approach 3: LinkedHashSet for Queue, and HashMap of Unique-Statuses
Intuition
While an amortized time of O(1) will always be better than a non-amortized time of a higher complexity class, say, O(N), non-amortized O(1) would be even better. The downside of amortized time complexities is that while the average time per method call is "good", some calls might be really slow. Imagine if every one-millionth Google search took 1,000,000 ms, and all the others took 1 ms. The amortized time would be 2 ms, which, in theory, sounds great! However, the one-in-a-million person waiting 16 minutes for their search results won't be very happy with Google! (There would probably be less bad press if every search operation just took 5 ms...).
Is there a way we could remove the amortization from the data structure we designed in Approach 2?
For this to happen, we'd need to have each "removal" happen with its corresponding add(); not during some arbitrary showFirstUnique() call in the future. This is the only way we could avoid having lots of "waiting" removal operations. How does this work, though? Didn't we already decide it was too difficult?
-
The trouble with doing the removal in the
add()method was that it leads to a worst-case O(N) search of the queue, and potentially a worst-case O(N) removal from the middle of a queue—if it's even possible (Java doesn't allow removals from the middle of a queue). -
Making the actual remove an O(1) operation isn't too difficult; we simply need to use a
LinkedList-based rather thanArray-based queue implementation. -
Searching a
LinkedListfor a value is still O(N), though. The only data structures that supports search in O(1) time are hash-sets and hash-maps. But these don't maintain the input order; aren't we just going around in circles now?
There is another, not so well known, data structure we can use here: LinkedHashSet. Note that in Python, we can use an OrderedDict to achieve the same functionality. If you have never heard of it, have a look at its specs before reading any further. Can you see how it solves our problem?
A LinkedHashSet is a HashSet-LinkedList hybrid. Like a HashSet, items can be found, updated, added, and removed in O(1) time. In addition, it puts links between the entries to keep track of the order they were added. Whenever an item is removed from the LinkedHashSet, the links are updated to point to the previous and next, just like they are in an ordinary LinkedList.
In essence, a LinkedHashSet is a type of queue that supports O(1) removals from the middle! This is exactly what we need to solve the problem. We can now do the removal in the add() method, and know that it is O(1).
Algorithm
Complexity Analysis
Let K be the length of the initial array passed into the constructor.
Let N be the total number of items added onto the queue so far (including those from the constructor).
-
Time complexity :
-
constructor: O(K).
For each of the K numbers passed into the constructor, we're making a call to
add(). As we will determine below, each call toadd()has a cost of O(1). Therefore, for the K numbers added in the constructor, we get a total cost of K⋅O(1)=O(K). -
add(): O(1).
Like before, we're performing a series of O(1) operations when
add()is called. Additionally, we're also removing the number from the queue if it had been unique, but now no longer is. Seeing as the queue is implemented as aLinkedHashSet, the cost of this removal is O(1).Therefore, we get an O(1) time complexity for
add(). -
showFirstUnique(): O(1).
This time around, the implementation for
showFirstUnique()is straightforward. It simply checks whether or not the queue contains any items, and if it does, it returns the first one (without removing it). This has a cost of O(1).
-
-
Space complexity : O(N).
Each number is stored up to once in the
LinkedHashSet, and up to once in theHashMap. Therefore, we get an overall space complexity of O(N).
Adding CPP solutions as well would be really helpful.
April 29, 2020 7:16 PM
My solution uses LinkedHashMap
class FirstUnique {
private Map<Integer, Integer> map;
public FirstUnique(int[] nums) {
map = new LinkedHashMap<>();
for(int x: nums) map.put(x, map.getOrDefault(x, 0) + 1);
}
public int showFirstUnique() {
for(int key: map.keySet()){
if(map.get(key) == 1) return key;
}
return -1;
}
public void add(int value) {
map.put(value, map.getOrDefault(value, 0) + 1);
}
}
November 23, 2020 8:58 PM
In the second python solution what is the need of doing self.queue = deque(nums)?? while we are calling add function for every number??
self.queue = deque() will work.
Instead of map we can use HashSet
class FirstUnique {
Set<Integer> isUnique = new HashSet<>();
Set<Integer> q = new LinkedHashSet<>();
public FirstUnique(int[] nums) {
for(int n: nums){
this.add(n);
}
}
public int showFirstUnique() {
if(!q.isEmpty()){
return q.iterator().next();
}
return -1;
}
public void add(int value) {
if(!isUnique.contains(value)){
isUnique.add(value);
q.add(value);
}
else {
q.remove(value);
}
}
}
April 29, 2020 5:37 PM
I loved the thought process - iterative, crisp, and clear. It does really well to expresses the problem-solving journey.
Hey, can someone help me with my cpp solution beats 18%. I tried implementing this using a combination of doubly linked list (supports O(1) delete operation anywhere) and a hashmap to simply store the value -> iterator pairing (so that I know where to delete) . But my solution runtime beats 18% and not more. Not sure where complexity is bad.
list<int> ddl;
unordered_map<int,int> cnt;
unordered_map<int,list<int>::iterator> hm;
FirstUnique(vector<int>& nums) {
loop(i, nums.size()){
add(nums[i]);
}
}
int showFirstUnique() {
if(ddl.size()==0) return -1;
list<int>::iterator a = ddl.begin();
return *(a);
}
void add(int value) {
if(cnt[value]==0) {
hm[value] = ddl.insert(ddl.end(), value);
}
else {
if(cnt[value]==1){
ddl.erase(hm[value]);
}
}
cnt[value]++;
}
According to an article I read, 'Insertion and deletion for doubly linked list at a known position is O(1). However, finding that position is O(n), unless it is the head or tail of the list.' Since I am inserting at the tail always, I assume it should be O(1). I mean even adding N elements to the end of a vector has amortized linear complexity, which translates to amortized constant per-item complexity so I am pretty sure add operation is O(1).
So complexity of
constructor: O(K)
add: O(1)
unordered_map find, add, increment - all O(1)
ddl insert at end of list - O(1)
ddl erase at known position - O(1)
showFirstUnique : Just getting the beginning of ddl and returning value O(1)
Overall most optimal time complexity.
Last Edit: May 9, 2021 3:17 AM
I don't think this is a good question. If someone doesn't know an unusual DS like LinkedHashSet or LinkedHashMap, he will fail the interview?
Can someone explain to me why the description makes it look like the queue is not getting dequeued for duplicates? According to this the queue should be [3,5,5,2,3] on last step? Am I missing something?
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
My answer was originally the 3rd answer, but on one of the 12th testcase: 698 was not first within the dictionary/ set if anyone knows why. I am using Python and it is a version above 3.5 where they should be automatically ordered by their insertion. I ended up having to implement my own doubly linked hashmap.
Edit:
Nvm I found the problem, apparently only dictionaries are ordered by default but not a set. Not sure why, but interesting.
Here's some more info:
https://stackoverflow.com/questions/45581901/are-sets-ordered-like-dicts-in-python3-6
Last Edit: January 24, 2021 6:01 AM
In approach 3, I think there is no need to put false in the map since there is no remove operation on the queue.
public void add(int value) {
if(!map.containsKey(value)){
map.put(value, true);
set.add(value);
}else{
set.remove(value);
}
}
You don't have any submissions yet.
xxxxxxxxxxclass FirstUnique {public: FirstUnique(vector<int>& nums) { } int showFirstUnique() { } void add(int value) { }};/** * Your FirstUnique object will be instantiated and called as such: * FirstUnique* obj = new FirstUnique(nums); * int param_1 = obj->showFirstUnique(); * obj->add(value); */